import java.util.*;

class Solution08 {
    public String alienOrder(String[] words) {
        // 创建哈希表
        Map<Character, List<Character>> hashMap = new HashMap<>();
        // 创建入度哈希表
        Map<Character, Integer> rudu = new HashMap<>();
        for (String s : words) {
            for (Character c : s.toCharArray()) {
                // 初始化为0
                rudu.put(c, 0);
            }
        }
        // 两层for循环进行遍历
        int m = words.length;
        for (int i = 0; i < m - 1; i++) {
            String s1 = words[i];
            String s2 = words[i + 1];
            int lengthMin = Math.min(s1.length(), s2.length());

            for (int j = 0; j < lengthMin; j++) {
                // 进行判断 讨论
                if (s1.charAt(j) != s2.charAt(j)) {
                    // 进行判断
                    if (!hashMap.containsKey(s1.charAt(j))) {
                        hashMap.put(s1.charAt(j), new ArrayList<>());
                    }
                    if (!hashMap.get(s1.charAt(j)).contains(s2.charAt(j))) {
                        // 进行添加
                        hashMap.get(s1.charAt(j)).add(s2.charAt(j));
                        // s2入度增加
                        rudu.put(s2.charAt(j), rudu.get(s2.charAt(j)) + 1);
                    }
                    break;
                }

                if (s1.length() > s2.length() && s1.startsWith(s2)) {
                    return "";
                }
            }
        }
        // 进行拓扑排序
        Queue<Character> q = new LinkedList<>();
        for (Character c : rudu.keySet()) {
            if (rudu.get(c) == 0) {
                // 添加到队列
                q.add(c);
            }
        }

        // 结果存储
        StringBuilder s = new StringBuilder();
        // 循环判断
        while (!q.isEmpty()) {
            Character t = q.poll();
            s.append(t);
            if (hashMap.get(t) != null) {
                for (Character c : hashMap.get(t)) {
                    // 更新入度
                    rudu.put(c, rudu.get(c) - 1);
                    // 进行判断
                    if (rudu.get(c) == 0) {
                        // 入队
                        q.add(c);
                    }
                }
            }
        }
        // 判断是否有环
        for (Character c : rudu.keySet()) {
            if (rudu.get(c) != 0) {
                return "";
            }
        }
        return s.toString();
    }
}